Known practice in motion estimation, ME, which is also specified in standard image coding systems such as MPEG2 and H264, is to estimate motion vectors for some macroblocks. A macroblock is a defined two-dimensional array of contiguous pixels selected from a current picture of a video sequence, aligned with a macroblock grid. A size and shape of the macroblock is usually specified in a relevant standard.
A transmitted motion vector for a current macroblock is a representation of a 2-dimensional shift which would be required to move a current macroblock to a position of a best match in a search area of a reference picture. The motion vector is used in a decoder to locate pixels from a previously received picture which provide the best match for the array of pixels in a macroblock to be decoded.
This match is performed at the encoder by searching in one or more chosen reference pictures nearby in the video sequence, typically within 10 frames, that have previously been encoded.
Since an order of encoding and transmission may be different from a display order of pictures, it is possible, and often useful, to predict macroblocks by transmitting motion vectors from previously encoded reference pictures that will not be displayed until after the current frame is displayed.
The motion estimation process described above is a computationally intensive task. It is important, therefore, to concentrate the search for the motion vector on an area of the reference image in which the best match is most likely to be found. Prior art is to use fixed rectangular search areas because they are convenient to process but they can waste valuable resources and time in searching areas where the best match vector is unlikely to be found. Moreover, statistics show that a best shape of this search area is not conveniently rectangular; strong diagonal motion, represented by the corners of a rectangular search window, is very rare in actual picture sequences.
It is an object of the present invention at least to ameliorate the aforesaid shortcomings in the prior art.